1. Field of the Invention
The present invention generally relates to techniques for computing a routability estimation for a floorplan of a circuit design. More specifically, the present invention relates to a system that redistributes route overflow values away from over-congested local routing regions, and towards under-congested local routing regions to compute a routability estimation on a floorplan.
2. Related Art
Performing a detailed routing operation for a circuit design's floorplan is an expensive process that can take several days to complete. To make matters worse, a detailed routing operation is not always guaranteed to succeed. Detailed routing is therefore not a practical process to use when experimenting on several versions of designs to assess routability.
A global router is commonly used as a first-pass routing tool for a given floorplan of a circuit design. It arranges routes across a floorplan by analyzing the floorplan as a collection of local routing regions, and by arranging the routes between the local routing regions. The global router produces a global route solution, which is then passed on to a detailed router to complete the routing task. It is common for the global route solution to include route overflows associated with a number of local routing regions. Unfortunately, these route overflows may or may not be resolved by the subsequent detailed routing operation.
Given that a detailed router is not always guaranteed to succeed, a global router also performs a simplistic routability analysis for a given floorplan to enable an engineer to predict whether a detailed router will be able to complete the routing operation. A successful routability analysis is important because it can allow an engineer to optimize a floorplan for routability before the floorplan is processed by a detailed router, thus preventing a number of wasted detailed routing efforts. A commonly used method for routability analysis comprises examining the percentage of local routing regions that have an overflow of routes after a global routing operation. In this analysis, an overflow is defined as the excess demand for available tracks compared to the overall capacity of the local routing regions. Typically, if the overflow percentage is greater than 2% for a floorplan, the floorplan is deemed unroutable. This method for estimating the routability of a design is not accurate given that it often leads to false positives, and can even lead to false negatives. Moreover, this method is limited in its analysis for the routability of a floorplan because it does not consider the capabilities and limitations of a detailed router.